#include <iostream>
#include <new>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
    public:
    vector<TreeNode*> genTrees(int begin, int end){
        vector<TreeNode*> res;
        if(begin==end){
            TreeNode* nullnode = nullptr;
            res.push_back(nullnode);
            return res;
        }
        else if(begin-end==1){
            TreeNode* node = new TreeNode(begin);
            res.push_back(node);
            return res;
        }
        else{
            for(int i=begin;i<end;i++){
                vector<TreeNode*> leftTrees = genTrees(begin,i);
                vector<TreeNode*> rightTrees = genTrees(i+1, end);
                for(TreeNode* le: leftTrees){
                    for(TreeNode* ri: rightTrees) {
                        TreeNode* node = new TreeNode(i, le, ri);
                        res.push_back(node);
                    }
                }
            }
            return res;
        }
    }
    vector<TreeNode*> generateTrees(int n) {
        return genTrees(1, n+1);
    }
};

int main() {

    return 0;
}